package com.fosss.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰计算器
 */
public class PolandNotation {
    public static void main(String[] args) {
        //将中缀表达式转为后缀表达式
        //1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -  结果为16
        List<String> list = toInfixList("(30+4)*5-6");
//        System.out.println(list);
//        System.out.println(toSuffixList(list));
        List<String> example = toSuffixList(list);

        //定义逆波兰表达式 (30+4)*5-6=> 30 4 + 5 * 6 -,     结果为164
        //为了方便，数字和符号之间用空格隔开
//        String example="30 4 + 5 * 6 -";
//        System.out.println(getString(example));
//        List<String> string = getString(example);

        System.out.println(calculator(example));
    }

    /**
     * 将中缀表达式的字符串转为list
     */
    public static List<String> toInfixList(String s) {
        List<String> list = new ArrayList<>();
        //如果时字符串，则直接存入list；如果是数字，则需要判断是否为多位数
        int i = 0;
        char c;
        String str = "";//用来拼接字符串
        do {
            if (((c = s.charAt(i)) < 48) || ((c = s.charAt(i)) > 57)) {
                list.add("" + c);
                i++;
            } else {
                str = "";//将字符串置空！！！！！！！！！
                while ((i < s.length()) && ((c = s.charAt(i)) >= 48) && ((c = s.charAt(i)) <= 57)) {
                    str += c;
                    i++;
                }
                list.add(str);
            }

        } while (i < s.length());
        return list;
    }

    /**
     * 将list转为后缀表达式
     *

     * 6) 重复步骤2至5，直到表达式的最右边

     */
    public static List<String> toSuffixList(List<String> ls) {
        // 1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2;
        Stack<String> operStack = new Stack<>();
        //因为整个过程中numStack没有pop操作，而且后续中还需要将numStack中的元素逆序输出，比较麻烦
        //因此这里直接用List代替numStack
//        Stack<String> numStack = new Stack<>();
        List<String> numStack = new ArrayList<>();
        //2) 从左至右扫描中缀表达式;
        for (String l : ls) {
            //3) 遇到数时，将其压入s2；
            if (l.matches("\\d+")) {
                numStack.add(l);
            }else if(l.equals("(")){
                //* 5) 遇到括号时：
                //如果是"(",直接入栈
                operStack.push(l);
            }else if(l.equals(")")){
                // 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，
                while (!operStack.peek().equals("(")) {
                    numStack.add(operStack.pop());
                }
                //此时将这一对括号丢弃!!!!!!!!!
                operStack.pop();

            } else {
                //4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
                //1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
                if (operStack.isEmpty() || operStack.peek().equals("(")) {
                    operStack.push(l);
                } else {
                    //2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
                    if (operStack.size()!=0&&priority(l)>priority(operStack.peek())){
                        operStack.push(l);
                    }else {
                        //若优先级小于等于栈顶运算符，则先将s1弹出添加到s2，再执行4.1
                        numStack.add(operStack.pop());
                        while (operStack.isEmpty() || operStack.peek().equals("(")){
                            operStack.push(l);
                        }
                    }
                }
            }
        }
        // 将s1中剩余的运算符依次弹出并压入s2
        // 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
        while (!operStack.isEmpty()){
            numStack.add(operStack.pop());
        }
        return numStack;
    }

    /**
     * 返回优先级（用数字表示）大小
     */
    public static int priority(String s) {
        switch (s) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
        }
        return - 1;
    }


    /**
     * 将字符串存到List中
     *
     * @param s
     * @return
     */
    public static List<String> getString(String s) {
        String[] split = s.split(" ");
        List<String> list = new ArrayList<>();
        for (String s1 : split) {
            list.add(s1);
        }
        return list;
    }

    /**
     * 进行计算
     */
    public static int calculator(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            if (s.matches("\\d+")) {//s为数字（正则表达式!!!!!）
                //直接入栈
                stack.add(s);
            } else {
                //s为符号,则弹出两个数进行运算，注意运算顺序！！！！！！！！
                int result = 0;
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                if (s.equals("+")) {
                    result = num1 + num2;
                } else if (s.equals("-")) {
                    result = num2 - num1;
                } else if (s.equals("*")) {
                    result = num1 * num2;
                } else if (s.equals("/")) {
                    result = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                //将运算结果入栈,注意转换类型
                stack.push(String.valueOf(result));
            }
        }
        //最后栈中存放的即为结果
        return Integer.parseInt(stack.pop());
    }
}
















